package com.github.tangmonkmeat;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * Description:
 *
 * @author zwl
 * @version 1.0
 * @date 2021/7/19 下午1:57
 */
public class 三个数字012排序 {

    public static void main(String[] args) {

        int[] array = new int[]{2,0,1};

        int[] sort = sort(array);

        System.out.println(Arrays.toString(sort));
    }

    public static int[] sort (int[] array) {
        if(array.length <= 1){
            return array;
        }
        int[] res = new int[array.length];
        LinkedList<Integer> temp = new LinkedList<>();
        temp.add(array[0]);
        int num0 = 1;
        for(int i = 1;i < array.length;i++){
            int value = array[i];
            if(value >= temp.getLast()){
                temp.addLast(value);
            }else if(value <= temp.getFirst()){
                int pre = temp.getFirst();
                temp.addFirst(value);
                if (value == pre){
                    num0++;
                }else {
                    num0 = 1;
                }
            }else {
                temp.add(num0,value);
            }
        }
        for(int j = 0;j < temp.size();j++){
            res[j] = temp.get(j);
        }
        return res;
    }
}
